package com.study.leetcode;

//https://leetcode-cn.com/problems/longest-palindromic-substring/
public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        int start;
        int end;
        String result = "";
        /**
         * 这里举一个例子  aaabb
         * 我们查找这个字符串的所有的回文字符串的时候需要将每一个位置开始沿着两侧检测是否有回文字符串
         * 所有位置的回文字符串的总和及为结果
         * 从当前位置查找回文串的时候有两种情况
         * 1.当前位置为回文串的中心（回文串的字符个数为奇数个）
         * 2.当前位置为回文串的中心之一（回文串的字符个数为偶数个，中心有两个字符串）
         */
        for (int i = 0; i < s.length(); i++) {
            //回文串从当前位置为中心开始，回文串字符数为奇数的情况
            //当前一个字符也算作一个回文串
            start = i;
            end = i;
            //往两边扩展如果符合条件就计数
            while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
                String sub = s.substring(start, end + 1);
                if (sub.length() > result.length()) {
                    result = sub;
                }
                start--;
                end++;
            }
            //回文串从当前位置为中心开始，回文串字符数为偶数的情况
            start = i;
            end = i + 1;
            //往两边扩展如果符合条件就计数
            while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
                String sub = s.substring(start, end + 1);
                if (sub.length() > result.length()) {
                    result = sub;
                }
                start--;
                end++;
            }
        }
        return result;
    }
}
